﻿//523.连续的子数组和
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = -1;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
            if (hash.count(sum % k))
            {
                if (i - hash[sum % k] > 1)
                {
                    return true;
                }
            }
            else
            {
                hash[sum % k] = i;
            }
        }
        return false;
    }
};

//64.最小路径和
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size(), col = grid[0].size();
        vector<vector<int>> dp(row + 1, vector<int>(col + 1, INT_MAX));
        dp[0][1] = 0;

        for (int i = 1; i <= row; i++)
        {
            for (int j = 1; j <= col; j++)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[row][col];
    }
};

//191.位1的个数
class Solution {
public:
    int hammingWeight(int n) {
        int ans = 0;
        for (int i = 0; i < 32; i++)
        {
            if ((n >> i) & 1 == 1)
            {
                ans++;
            }
        }
        return ans;
    }
};

//338.比特位计数
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1);

        for (int i = 0; i <= n; i++)
        {
            if (i % 2 == 0)
            {
                ans[i] = ans[i / 2];
            }
            else
            {
                ans[i] = ans[i - 1] + 1;
            }
        }
        return ans;
    }
};

//461.汉明距离
class Solution {
public:
    int hammingDistance(int x, int y) {
        int ans = 0, tem = x ^ y;
        for (int i = 0; i < 32; i++)
        {
            if ((tem >> i) & 1 == 1)
            {
                ans++;
            }
        }
        return ans;
    }
};

//260.只出现一次的数字III
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        int size = nums.size();
        unsigned int value = 0;
        for (int i = 0; i < size; i++)
        {
            value ^= nums[i];
        }

        int pos = 0;
        for (int i = 0; i < 32; i++)
        {
            if ((value >> i) & 1 == 1)
            {
                pos = i;
                break;
            }
        }

        int sum1 = 0, sum2 = 0;
        for (int i = 0; i < size; i++)
        {
            if ((nums[i] >> pos) & 1 == 1)
            {
                sum1 ^= nums[i];
            }
            else
            {
                sum2 ^= nums[i];
            }
        }

        return { sum1, sum2 };
    }
};

